package com.easy.leetcode.dp;

//64. 最小路径和
public class MinPathSum64 {
    public int minPathSum(int[][] grid) {
        //行
        int row = grid.length;
        //列
        int column = grid[0].length;
        //定义动态转移方程，dp为到该位置的最小路径
        //int[][] dp = new int[row][column];
        //遍历矩阵
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                //定义初始值，dp[0][0] 是grid[0][0]
                if (i == 0 && j == 0) {
                    grid[i][j] = grid[i][j];
                } else if (i == 0 && j > 0) {//第一行，只能来自于左边
                    grid[i][j] = grid[i][j - 1] + grid[i][j];
                } else if (j == 0 && i > 0) {//第一列只能来自于上边
                    grid[i][j] = grid[i - 1][j] + grid[i][j];
                } else {//其他，上边和左边的最小值加上当前值
                    grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
                }
            }
        }
        return grid[row - 1][column - 1];
    }
}
